'''
https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/description/
'''
from functools import cache
from typing import List


class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])

        @cache
        def f(i, j):
            res = 1
            for tx, ty in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
                if 0 <= tx < m and 0 <= ty < n and matrix[i][j] < matrix[tx][ty]:
                    res = max(res, f(tx, ty))
            return res + 1
        ans = 0
        for i in range(m):
            for j in range(n):
                ans = max(ans, f(i, j))
        return ans - 1

    def longestIncreasingPath2(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        # 依赖4个方向，不太容易直接打表实现啊
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        return max(max(row) for row in dp) - 1
